package com.tingyuge.base.thread.wang.collection;

import java.util.Random;

/**
 * Created by xiaodao
 * date: 2019/12/23
 */
public class SimpleSkipList {

    private final static byte HEAD_NODE = (byte)-1;
    private final static byte TAIL_NODE = (byte)-1;
    private final static byte DATA_BIT = (byte)0;

    private static class Node{
        private Integer value;
        private Node up, down,left,right;

        private byte bit;
        public Node(Integer integer,byte bit){
            this.value = integer;
            this.bit = bit;
        }

        public Node(Integer value) {
            this.value = value;
        }
    }

    private Node head;
    private Node tail;
    private int size;
    private int height;
    private Random random;

    public SimpleSkipList(){
        this.head = new Node(null,HEAD_NODE);
        this.tail = new Node(null,TAIL_NODE);
        head.right = tail;
        tail.left = head;
        this.random = new Random(System.currentTimeMillis());
    }

    public boolean isEmpty(){
        return (getSize() == 0);
    }
    public int getSize(){
        return size;
    }

    public Node find(Integer element){
        Node current = head;
        for(;;){
            while (current.right.bit!=TAIL_NODE && current.right.value <= element){
                current = current.right;
            }
            if(current.down !=null){
                current = current.down;
            }else {
                break;
            }
        }
        //这个元素 小于  current <=element <current.right (if exist)
        return current;
    }

    public void add(Integer element){
        Node nearNode = this.find(element);
        Node newNode = new Node(element);
        newNode.left = nearNode;
        newNode.right = nearNode.right;
        nearNode.right.left = newNode;
        nearNode.right = newNode;

        int currentLevel = 0;
        while (random.nextDouble() < 0.3d){
            //新创建一层
            if(currentLevel >= height){
                height ++;
                Node dumyHead =  new Node(null,HEAD_NODE);
                Node dumyTail =  new Node(null,TAIL_NODE);

                dumyHead.right = dumyTail;
                dumyHead.down = head;
                head.up = dumyHead;
                dumyTail.left = dumyHead;
                dumyTail.down = tail;
                tail.up = dumyTail;
                head = dumyHead;

            }

            while ((nearNode !=null) && nearNode.up ==null){
                nearNode = nearNode.left;
            }
            nearNode = nearNode.up;

            Node upNode = new Node(element);
            upNode.left = nearNode;
            upNode.right = nearNode.right;
            upNode.down = newNode;

            nearNode.right.left = upNode;
            nearNode.right  = upNode;

            newNode.up = upNode;

            newNode =upNode;

            currentLevel ++;
        }
        size ++;
    }

    public void dumpSkipList(){
       Node temp = head;
       int i = height +1;
       while (temp !=null){
           System.out.printf("total [%d] height [%d]",height+1,i--);
           Node node = temp.right;
           while (node.bit == DATA_BIT){
               System.out.printf("->%d",node.value);
               node = node.right;


           }
           System.out.printf("\n");
           temp = temp.down;

       }
        System.out.println("======");
    }


    public boolean contains(Integer element){
        Node node = this.find(element);
        return (node.value == element);
    }

    public Integer get(Integer element){
        Node node = this.find(element);
        return (node.value == element)? node.value: null;
    }

    public static void main(String[] args) {
        SimpleSkipList simpleSkipList =  new SimpleSkipList();
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < 50; i++) {
            simpleSkipList.add(random.nextInt(1000));
        }
        simpleSkipList.dumpSkipList();
    }

}
